﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Draco.DataStructure;

namespace Draco.Algorithms
{
    public class D_Sort
    {


        /// <summary>
        /// 将数据排序后返回数据的索引
        /// </summary>
        /// <param name="dateArray">数据数组</param>
        /// <returns>数据的索引</returns>
        public static int[] QuickSortIndex(int[] dateArray)
        {
            int length = dateArray.Length;
            int[] result = new int[length];
            IntStruct[] resultStructs =  new IntStruct[length];
            for (int i = 0; i < length; i++)
            {
                resultStructs[i].index = i;
                resultStructs[i].value = dateArray[i];
            }
            QuickSort(resultStructs,0, length-1);
            for (int i = 0; i < length; i++)
            {
                result[i] = resultStructs[i].index;
            }
            return result;
        }

        /// <summary>
        /// 将数据排序后返回数据的索引
        /// </summary>
        /// <param name="dateArray">数据数组</param>
        /// <returns>数据的索引</returns>
        public static int[] QuickSortIndex(string[] dateArray)
        {
            int length = dateArray.Length;
            int[] result = new int[length];
            StringStruct[] resultStructs = new StringStruct[length];
            for (int i = 0; i < length; i++)
            {
                resultStructs[i].index = i;
                resultStructs[i].value = dateArray[i];
            }
            QuickSort(resultStructs, 0, length - 1);
            for (int i = 0; i < length; i++)
            {
                result[i] = resultStructs[i].index;
            }
            return result;
        }


        private static void QuickSort(IntStruct[] dataArray, int left, int right)
        {
            if (left < right)
            {
                IntStruct x = dataArray[left];
                int i = left;
                int j = right;

                while (i != j)
                {
                    for (; i < j; j--)
                    {
                        if (dataArray[j].value <= x.value)
                        {
                            dataArray[i] = dataArray[j];
                            break;
                        }
                    }
                    for (; i < j; i++)
                    {
                        if (dataArray[i].value > x.value)
                        {
                            dataArray[j] = dataArray[i];
                            break;
                        }
                    }
                }

                dataArray[i] = x;

                QuickSort(dataArray,left,i-1);
                QuickSort(dataArray,i+1,right);
            }
        }

        private static void QuickSort(StringStruct[] dataArray, int left, int right)
        {
            if (left < right)
            {
                StringStruct x = dataArray[left];
                int i = left;
                int j = right;

                while (i != j)
                {
                    for (; i < j; j--)
                    {
                        if (dataArray[j].value.CompareTo(x.value)<=0)
                        {
                            dataArray[i] = dataArray[j];
                            break;
                        }
                    }
                    for (; i < j; i++)
                    {
                        if (dataArray[i].value.CompareTo(x.value)>0)
                        {
                            dataArray[j] = dataArray[i];
                            break;
                        }
                    }
                }

                dataArray[i] = x;

                QuickSort(dataArray, left, i - 1);
                QuickSort(dataArray, i + 1, right);
            }
        }

        private struct IntStruct
        {
            public int index;
            public int value;
        }

        private struct StringStruct
        {
            public int index;
            public string value;
        }

    }

    

}
